package week06

import "math"

// 322. 零钱兑换
// https://leetcode-cn.com/problems/coin-change/

func coinChange(coins []int, amount int) int {
	var f = make([]int, amount+1)
	for i := 1; i <= amount; i++ {
		f[i] = math.MaxInt32
		for _, coin := range coins {
			if i - coin >= 0 {
				f[i] = min(f[i], f[i-coin] + 1)
			}
		}
	}
	if f[amount] == math.MaxInt32 {
		return -1
	}
	return f[amount]
}

func min(x, y int) int {
	if x > y {
		return y
	}
	return x
}